package com.demo.java.OD401_450.OD402;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【Family Day(C&D卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146250069
 */
public class OdMain {
    // 计算从(0, 0)到(m-1, n-1)的不同路径数量
    public static int countPaths(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        // 创建一个二维数组来存储路径数量
        int[][] dp = new int[m][n];

        // 初始化第一行和第一列
        dp[0][0] = 1;
        for (int i = 1; i < m; i++) {
            dp[i][0] = (grid[i][0] == 0) ? dp[i - 1][0] : 0;  // 只有当前格子可进入，才可以累加路径
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = (grid[0][j] == 0) ? dp[0][j - 1] : 0;  // 同理，处理第一行
        }

        // 填充数组
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (grid[i][j] == 0) {  // 只有当当前格子可进入时，才能从上方或左方累加路径
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }

        return dp[m - 1][n - 1];  // 返回终点的路径数
    }

    // 读入输入
    public static int[][] readInput() {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int[][] grid = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }
        return grid;
    }

    // 主程序
    public static void main(String[] args) {
        int[][] grid = readInput();
        int result = countPaths(grid);
        System.out.println(result);  // 输出路径数量
    }
}